package demo.DataStrucAndAlgo.Tree.RadBlackTree;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/9-08-09-16:08
 * @Description：demo.DataStrucAndAlgo.Tree.RadBlackTree   红黑树
 */
/*
红黑树：
        是一种二叉查找树，在二叉查找树的基础上额外添加了一个标记，同时具有一定的规则。这些规则使红黑树保证了一种平衡
    插入、删除、查找的最坏时间复杂度都为O(log n)
    HashMap、TreeMap、TreeMap都应用了红黑树

    黑色高度
        从根节点到叶节点的路径上黑色结点的个数
    红黑树5个特性
        1、每个结点要么是红色，要么是黑色
        2、根节点永远是黑色的；
        3、所有的叶节点都是黑色的（NIL结点）但java实现的红黑树将使用null来代表空结点，所以遍历红黑树时看不到黑色叶子结点，
        反而看到每个叶子结点都是红色的。
        4、每个红色结点的两个子节点一定都是黑色，每个根到结点的路径上不会有两个连续的红色结点，但黑色结点可以。
        因此若给定黑色结点的个数N，最短路经的情况是连续的N个黑色，树的高度为N-1；最长路径的情况为结点红黑相间，树的高度为2(n-1)
        5、从任一结点到其子树中每个叶子结点的路径都包含相同数量的黑色结点；
 */
public class rad_black_tree {
}
